package com.leetcode.algorithm.y19.m01;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * leetcode-cn.com
 * 
 * (done)832. 翻转图像
 * (done)804. 唯一摩尔斯密码词
 * (done)922. 按奇偶排序数组 II
 * (done)944. 删列造序
 * (done)852. 山脉数组的峰顶索引
 * (done)728. 自除数
 * @author: jie.deng
 * @time: 2019年1月22日 上午9:52:13
 */
public class MySolution0122 {
    
	/**
	 * 832. 翻转图像
	 * 
     * 给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。
     * 
     * 水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。
     * 
     * 反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。例如，反转 [0, 1, 1] 的结果是 [1, 0, 0]。
     * 
     * 示例 1:
     * 
     * 输入: [[1,1,0],[1,0,1],[0,0,0]]
     * 输出: [[1,0,0],[0,1,0],[1,1,1]]
     * 解释: 首先翻转每一行: [[0,1,1],[1,0,1],[0,0,0]]；
     *      然后反转图片: [[1,0,0],[0,1,0],[1,1,1]]
     * 示例 2:
     * 
     * 输入: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
     * 输出: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
     * 解释: 首先翻转每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]；
     *      然后反转图片: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
     * 说明:
     * 
     * 1 <= A.length = A[0].length <= 20
     * 0 <= A[i][j] <= 1
	 * @param A
	 * @return
	 */
	public int[][] flipAndInvertImage(int[][] A) {
		// 水平翻转
		for (int[] arr : A) {
			int f = 0;
			int e = arr.length - 1;
			while (f < e) {
				if (arr[f] != arr[e]) {
					arr[f] = arr[f] ^ 1;
					arr[e] = arr[e] ^ 1;
				}
				f++;
				e--;
			}
		}
		// 反转
		for (int[] arr : A) {
			for (int i = 0; i < arr.length; i++) {
				arr[i] = arr[i] ^ 1;
			}
		}
		return A;
	}
	
	/**
	 * 804. 唯一摩尔斯密码词
	 * 
     * 国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串， 比如: "a" 对应 ".-", "b" 对应 "-...", "c" 对应 "-.-.", 等等。
     * 
     * 为了方便，所有26个英文字母对应摩尔斯密码表如下：
     * 
     * [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
     * 给定一个单词列表，每个单词可以写成每个字母对应摩尔斯密码的组合。例如，"cab" 可以写成 "-.-..--..."，(即 "-.-." + "-..." + ".-"字符串的结合)。我们将这样一个连接过程称作单词翻译。
     * 
     * 返回我们可以获得所有词不同单词翻译的数量。
     * 
     * 例如:
     * 输入: words = ["gin", "zen", "gig", "msg"]
     * 输出: 2
     * 解释: 
     * 各单词翻译如下:
     * "gin" -> "--...-."
     * "zen" -> "--...-."
     * "gig" -> "--...--."
     * "msg" -> "--...--."
     * 
     * 共有 2 种不同翻译, "--...-." 和 "--...--.".
     *  
     * 
     * 注意:
     * 
     * 单词列表words 的长度不会超过 100。
     * 每个单词 words[i]的长度范围为 [1, 12]。
     * 每个单词 words[i]只包含小写字母。
	 * @param words
	 * @return
	 */
    public int uniqueMorseRepresentations(String[] words) {
		if (words == null) {
			return 0;
		}
		String[] pwds = new String[] { 
				".-", "-...", "-.-.", "-..", ".", "..-.", "--.", 
				"....", "..", ".---", "-.-", ".-..", "--", "-.", 
				"---", ".--.", "--.-", ".-.", "...", "-", 
				"..-", "...-", ".--", "-..-", "-.--","--.." };
		Set<String> set = new HashSet<String>();
		for (String word : words) {
			StringBuilder sbStr = new StringBuilder();
			char[] arr = word.toCharArray();
			for (int i = 0; i < arr.length; i++) {
				sbStr.append(pwds[arr[i] - 'a']);
			}
			set.add(sbStr.toString());
		}
		return set.size();
    }
    
    /**
     * 922. 按奇偶排序数组 II
     * 
     * 给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
     * 
     * 对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
     * 
     * 你可以返回任何满足上述条件的数组作为答案。
     * 
     *  
     * 
     * 示例：
     * 
     * 输入：[4,2,5,7]
     * 输出：[4,5,2,7]
     * 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
     *  
     * 
     * 提示：
     * 
     * 2 <= A.length <= 20000
     * A.length % 2 == 0
     * 0 <= A[i] <= 1000
     * @param A
     * @return
     */
	public int[] sortArrayByParityII(int[] A) {
		int len = A.length;
		int evenIdx = 0;
		int oddIdx = 1;
		while (oddIdx <= len - 1 && evenIdx <= len - 2) {
			while (evenIdx <= len - 2 && A[evenIdx] % 2 == 0) {
				evenIdx += 2;
			}
			while (oddIdx <= len - 1 && A[oddIdx] % 2 == 1) {
				oddIdx += 2;
			}
			if (oddIdx <= len - 1 && evenIdx <= len - 2) {
				A[evenIdx] = A[evenIdx] ^ A[oddIdx];
				A[oddIdx] = A[evenIdx] ^ A[oddIdx];
				A[evenIdx] = A[evenIdx] ^ A[oddIdx];
				evenIdx += 2;
				oddIdx += 2;
			}
		}
		return A;
	}
    
    /**
     * 944. 删列造序
     * 
     * 给定由 N 个小写字母字符串组成的数组 A，其中每个字符串长度相等。
     * 
     * 选取一个删除索引序列，对于 A 中的每个字符串，删除对应每个索引处的字符。 所余下的字符串行从上往下读形成列。
     * 
     * 比如，有 A = ["abcdef", "uvwxyz"]，删除索引序列 {0, 2, 3}，删除后 A 为["bef", "vyz"]， A 的列分别为["b","v"], ["e","y"], ["f","z"]。（形式上，第 n 列为 [A[0][n], A[1][n], ..., A[A.length-1][n]]）。
     * 
     * 假设，我们选择了一组删除索引 D，那么在执行删除操作之后，A 中所剩余的每一列都必须是 非降序 排列的，然后请你返回 D.length 的最小可能值。
     * 
     * 示例 1：
     * 
     * 输入：["cba", "daf", "ghi"]
     * 输出：1
     * 解释：
     * 当选择 D = {1}，删除后 A 的列为：["c","d","g"] 和 ["a","f","i"]，均为非降序排列。
     * 若选择 D = {}，那么 A 的列 ["b","a","h"] 就不是非降序排列了。
     * 示例 2：
     * 
     * 输入：["a", "b"]
     * 输出：0
     * 解释：D = {}
     * 示例 3：
     * 
     * 输入：["zyx", "wvu", "tsr"]
     * 输出：3
     * 解释：D = {0, 1, 2}
     * 提示：
     * 
     * 1 <= A.length <= 100
     * 1 <= A[i].length <= 1000
     * @param A
     * @return
     */
	public int minDeletionSize(String[] A) {
		if (A == null || A.length == 1) {
			return 0;
		}
		int count = 0;
		int lenR = A.length;
		int lenC = A[0].length();
		for (int i = 0; i < lenC; i++) {
			for (int j = 0; j < lenR - 1; j++) {
				if (A[j + 1].charAt(i) < A[j].charAt(i)) {
					count++;
					break;
				}
			}
		}
		return count;
	}
    
    /**
     * 852. 山脉数组的峰顶索引
     * 
     * 我们把符合下列属性的数组 A 称作山脉：
     * 
     * A.length >= 3
     * 存在 0 < i < A.length - 1 使得A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
     * 给定一个确定为山脉的数组，返回任何满足 A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] 的 i 的值。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：[0,1,0]
     * 输出：1
     * 示例 2：
     * 
     * 输入：[0,2,1,0]
     * 输出：1
     *  
     * 
     * 提示：
     * 
     * 3 <= A.length <= 10000
     * 0 <= A[i] <= 10^6
     * A 是如上定义的山脉
     * @param A
     * @return
     */
	public int peakIndexInMountainArray(int[] A) {
		int len = A.length;
		for (int i = 0; i < len - 1; i++) {
			if (A[i] > A[i + 1]) {
				return i;
			}
		}
		return 0;
	}
    
    /**
     * 728. 自除数
     * 
     * 自除数 是指可以被它包含的每一位数除尽的数。
     * 
     * 例如，128 是一个自除数，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
     * 
     * 还有，自除数不允许包含 0 。
     * 
     * 给定上边界和下边界数字，输出一个列表，列表的元素是边界（含边界）内所有的自除数。
     * 
     * 示例 1：
     * 
     * 输入： 
     * 上边界left = 1, 下边界right = 22
     * 输出： [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
     * 注意：
     * 
     * 每个输入参数的边界满足 1 <= left <= right <= 10000。
     * @param left
     * @param right
     * @return
     */
	public List<Integer> selfDividingNumbers(int left, int right) {
		List<Integer> list = new ArrayList<Integer>();

		for (int i = left; i <= right; i++) {
			if (("" + i).contains("0")) {
				continue;
			}
			int j = i;
			boolean flag = true;
			while (j > 0) {
				int r = j % 10;
				if (i % r != 0) {
					flag = false;
					break;
				}
				j = j / 10;
			}
			if (flag) {
				list.add(i);
			}
		}

		return list;
	}
}
